/*
设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。

如果指定节点没有对应的“下一个”节点，则返回null。

示例 1:

输入: root = [2,1,3], p = 1

  2
 / \
1   3

输出: 2
示例 2:

输入: root = [5,3,6,2,4,null,null,1], p = 6

      5
     / \
    3   6
   / \
  2   4
 /   
1

输出: null

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/successor-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include "../stdc++.h"

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

// 中序遍历，迭代，栈
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        stack<TreeNode*> stk;
        TreeNode* pre = nullptr;
        TreeNode* cur = root;
        while (!stk.empty() || cur != nullptr) {
            while (cur != nullptr) {
                stk.push(cur);
                cur = cur->left;
            }
            cur = stk.top();
            stk.pop();
            if (pre == p) {
                return cur;
            }
            pre = cur;
            cur = cur->right;
        }
        return nullptr;
    }
};

// 中序遍历，递归
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        if (root == nullptr || p == nullptr) {
            return nullptr;
        }
        this->p = p;
        inorderSuccessor(root);
        return res;
    }
private:
    void inorderSuccessor(TreeNode* root) {
        if (root == nullptr) {
            return;
        }
        if (root->left) inorderSuccessor(root->left);
        if (pre == p && res == nullptr) {
            res = root; // res第一次赋值才行
            return;
        }
        pre = root;
        if (root->right) inorderSuccessor(root->right);
    }
private:
    TreeNode* p = nullptr;
    TreeNode* pre = nullptr;
    TreeNode* res = nullptr;
};

// 利用二叉搜索树的性质
class Solution {
public:
    TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
        TreeNode* res = nullptr;
        if (p->right != nullptr) { // 有右子树就找到右子树中的最左节点
            res = p->right;
            while (res->left != nullptr) {
                res = res->left;
            }
            return res;
        }
        TreeNode* node = root;
        while (node != nullptr) {
            if (node->val > p->val) { // 如果node的值比p的值大，那么后继节点可能是node或者node的左子树中
                res = node;
                node = node->left;
            } else { // 如果node的值比p的值小或等于，那么后继节点可能是node的右子树中
                node = node->right;
            }
        }
        return res;
    }
};
